package graphAlg.smallesttree;

import graphAlg.Edge;
import graphAlg.Graph;
import graphAlg.GraphGenerator;
import graphAlg.Node;
import graphAlg.unioncollection.UnionFind;


import java.util.*;

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;

public class Kruskal {
    public static void main(String[] args) {
        Graph graph = GraphGenerator.createGenerateGraph(new int[][]{
                {1, 2, 3},
                {1, 3, 4},
                {1, 4, 5},
                {2, 3, 6},
                {3, 4, 7},
                {2, 5, 8},
                {3, 5, 9},
                {4, 6, 10},
                {6, 7, 11}
        });
        List<Edge> edges = kruskalMST(graph);
        for(Edge edge : edges){
            System.out.println(edge.weight);
        }
    }


    public static List<Edge> kruskalMST(Graph graph){
        UnionFind unionFind = new UnionFind();
        unionFind.initUnionFind(graph);
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(((o1, o2) -> o1.weight - o2.weight));
        for(Edge edge : graph.edges){
            priorityQueue.add(edge);
        }
        List<Edge> result = new ArrayList<>();
        while(!priorityQueue.isEmpty()){
            Edge edge = priorityQueue.poll();
            if(!unionFind.isSameSet(edge.from,edge.to)){
                result.add(edge);
                unionFind.union(edge.from,edge.to);
            };
        }
        return result;

    }

}
